The development of the EDVAC computer system of 1948 is often cited as the beginning of the computer era. Since that time, computer systems have evolved into extremely sophisticated devices that may be found in many different settings. Computer systems typically include a combination of hardware (e.g., semiconductors, integrated circuits, circuit boards, etc.) and software (e.g., computer programs).
The typical design methodology for integrated circuit designs—such as very large scale integrated (VLSI) circuits and application specific integrated circuits (ASICs)—is conventionally divided into the following three stages. First, a design capture step is performed using, for example, a high-level language synthesis package. Next, design verification is made on the resulting design. This includes simulations, timing analysis, and automatic test pattern generation (ATPG) tools. Finally, there is layout and eventual tape out of the device. The device is then tested, and the process may need to be reiterated one or more times until the desired design criteria are satisfied.
The design capture step typically involves the specification of a logic circuit by a designer. A hardware description language (“HDL”) provides the designer with a mechanism for describing the operation of the desired logic circuit in a technology-independent manner.
Automated software tools available from companies such as Cadence Design Systems and Synopsys take an HDL description of the integrated circuit (sometimes referred to as a behavioral or register-transfer-level description) and map it into an equivalent netlist composed of the standard cells from a selected standard cell library. This process is commonly known as “synthesis.”
A netlist is a data structure representation of the electronic logic system that comprises a set of modules, each of which comprises a data structure that specifies sub-components and their interconnection. The netlist describes the way standard cells and blocks are interconnected. Netlists are typically available in Verilog, EDIF (Electronic Design Interchange Format), or VHDL (Very High Speed Integrated Circuit Hardware Design Language) formats. Other software tools available from companies such as Cadence or Synopsys take a netlist comprised of standard cells and create a physical layout of the chip by placing the cells relative to each other to minimize timing delays or wire lengths, and then create electrical connections (or routing) between the cells to physically complete the desired circuit. Once a netlist has been generated from the logic design, silicon compilers, also called place and route tools, convert the netlist into a semiconductor circuit layout. The semiconductor circuit layout specifies the physical implementation of the circuit in silicon or other semiconductor materials.
Design verification involves verifying that the logic definition is correct, that the circuit implements the function expected by the designers, and that the many optimizations and transformations introduced during the design process do not alter the intended logical function of the design. Design verification typically occupies a large portion of the schedule for any chip development cycle. Design verification may involve timing analysis and simulation tools. The data representation in the logic design database may be reformatted as needed prior to use by the timing analysis and simulation tools. The design undergoes design verification analysis in order to detect flaws in the design. The design is also analyzed using simulation tools to assess the functionality of the design. If errors are found or the resulting functionality is unacceptable, the designer modifies the design as needed. These design iterations help to ensure that the design satisfies its requirements. Formal verification (property checking) may also be used to prove correct behavior for selected aspects of the design. Formal verification is a technique that models a logic circuit as a state transition system using specifications for components in the system.
Another verification method is to generate large numbers of testcases or test programs. A traditional strategy is to manually write directed testcases that exercise specified parts of the design and run those testcases on a simulator that models the device operation. Writing such testcases is very time consuming and lacks random testing, which means covering all the legal or valid combinations of stimuli may be difficult. Also, the testcases written in this way are difficult to maintain because they lack portability and are vulnerable to any and all design changes, which causes significant modifications to the testcase bucket or regression test suite for almost every design change.
Another approach to creating testcases is to use a random testcase generator, which is often a script written in any high level language (e.g., C, C++, Perl, etc) that requires the verification engineer to provide some input as to what type of testcase is required. The testcase generator than randomly generates testcases based on the input type. “Type” means the commands, legal or valid ranges, and/or values for various parameters that need to be varied/changed in order to test the design. The type may be passed to the testcase generator as a file (e.g., a parameter file). The valid commands, parameter ranges, and/or values are defined based on the design specification and the directedness of the testcases required. This approach, besides providing comparatively increased random testing, also reduces the time required to generate testcase buckets or regression test suites because the job of the verification engineer is now merely to provide the constraints to the testcase generator after understanding the design specifications and verification environment. A few handwritten directed testcases may still be required to cover specific logic areas of the design.
Although testcase generators can enable testing that is more random and easier to modify, they still rely on the pseudo-randomness of the particular testcase generator. This can be a problem, as shown below, by observing that the testcases generated, even when employing a fairness algorithm, are not always as random as the verification engineer would hope. That is, a mismatch can occur in the generated commands/ranges/values in the testcase versus the expected commands/ranges/values.
To understand this mismatch, consider the following example: the verification engineer's objective is to generate a number (“n”) testcases where n/2 should be read testcases and the other n/2 should be write testcases. Unfortunately, a testcase generator using an algorithm with a 50% probability of choosing a read testcase and a 50% probability of choosing a write testcase actually has only a 31.25% probability of generating equal number of reads and writes when n=6 and only a 14.44% probability of generating equal numbers of reads and writes when n=30. Hence, relying on a fairness algorithm of the typical testcase generator is not sufficient to meet the verification engineer's objective.
The calculations that result in the aforementioned 31.25% and 14.44% are as follows. For a sequence of n=6 testcases, each needing to choose between two equally probable choices, reads or writes, the total possibilities of testcase combinations are 26=64. Out of these 64 combinations, the only combinations of interest are the ones that have exactly 3 reads and 3 writes. Thus, the number of combinations of interest is: 6C3=[6!]/[3!×3!]=720/(6×6)=20. Finally, the probability of generating exactly 3 reads and 3 writes is: 20/64×100=31.25%.
Similarly, for a sequence of 30 testcases, each needing to choose between two equally probable choices, reads or writes, the total possibilities of testcase combinations are 230=1,073,741,824. Out of these 1,073,741,824 combinations, the only combinations of interest are the ones that have exactly 15 reads and 15 writes. Thus, the number of combinations of interest is: 30C15=[30!]/[15!×15!]=155,117,520. Finally, the probability of generating exactly 15 reads and 15 writes is: [155,117,520]/[1,073,741,824]×100=14.44%.
Thus, without a better way to generate testcases, testing of devices will continue to suffer with a lack of complete coverage. Although the aforementioned problems have been described in the context of a netlist, they may occur in any type of device under test, whether a simulated device, a software program, or a hardware device.